package algorithm_demo.demo05;

/**
 * 从左到右的尝试模型
 * 给定两个长度为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值
 * 给定一个正数bag，表示一个载重bag的袋子
 * 你装的物品不能超过这个重量，返回你能装下最多的价值是多少
 *
 * @author Api
 * @date 2023/3/6 23:34
 */
public class Code06_Knapsack {
    //第一种
    public static int getMaxValue(int[] weights, int[] values, int bag) {
        return process(weights, values, 0, 0, bag);
    }

    /**
     * 不变：w[],v[] bag
     *
     * @param w
     * @param v
     * @param index    最大价值
     * @param alreadyW 0--index-1上做了货物的选择，使得你已经达到的重量是多少
     * @param bag
     * @return 如果返回-1，认为没有方案，如果不返回-1，则认为是一个真实的价值
     */
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        if (alreadyW > bag) {
            return -1;
        }
        //重量没超
        if (index == w.length) {
            return 0;
        }
        //p1没有要当前货的情况
        int p1 = process(w, v, index + 1, alreadyW, bag);
        //p2Next要了当前的货物的重量，后面的货产生的最大价值
        int p2Next = process(w, v, index + 1, alreadyW + w[index], bag);
        int p2 = -1;
        if (p2Next != -1) {
            p2 = v[index] + p2Next;
        }
        return Math.max(p1, p2);
    }


    //第二种
    public static int maxValue(int[] weights, int[] values, int bag) {
        return process(weights, values, 0, bag);
    }

    /**
     * 只剩下rest的空间了
     * index...货物自由选择，但是剩余空间不要小于0
     * 返回index...货物能够获得的最大价值
     *
     * @param weights
     * @param values
     * @param index
     * @param rest
     * @return
     */
    public static int process(int[] weights, int[] values, int index, int rest) {
        //base case 1  小于0的情况
        if (rest < 0) {
            return -1;
        }
        //base case 2  大于等于0的情况
        if (index == weights.length) {
            return 0;
        }
        //有货物也有空间
        int p1 = process(weights, values, index + 1, rest);
        int p2 = -1;
        int p2Next = process(weights, values, index + 1, rest - weights[index]);
        if (p2Next != -1) {
            p2 = values[index] + p2Next;
        }
        return Math.max(p1, p2);
    }

    /*动态规划*/
    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        //dp[N][...] = 0
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = -1;
                if (rest - w[index] >= 0) {
                    p2 = v[index] + dp[index + 1][rest - w[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }


}
